import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;

/** Cette classe permet de définir la liste des candidats de noeuds suivants
 * que la fourmi peut choisir, ainsi que les fonctions et les méthodes
 * qui permettent de mettre à jour cette liste.
 * Le but est d'améliorer la rapidité de l'algorithme en réduisant le choix 
 * des noeuds suivants à une liste de candidats.
 * @author Pocman
 *
 */
public class AntListeCandidat {

	private static ArrayList<ArrayList<Arc>> distances;
	private static AntInstance antInstance;
	private static int nbSommet;
	private boolean[] noeudAVisiter;
	private static int nbNoeudsVoisins;
	private int noeudVisite;
	
	/** méthode qui initialise la liste des candidats
	 * @param antInstance
	 * @throws Exception
	 */
	public static void initialisationListeCandidat(AntInstance antInstance) throws Exception{
		AntListeCandidat.antInstance = antInstance;
		AntListeCandidat.nbSommet = AntListeCandidat.antInstance.getInstance().getNbSommets();
		AntListeCandidat.nbNoeudsVoisins = 50;
		AntListeCandidat.distances = new ArrayList<ArrayList<Arc>>();
		
	
		for (int i=0; i<AntListeCandidat.nbSommet; i++){
			AntListeCandidat.distances.add(new ArrayList<Arc>());
			for (int j=0; j<AntListeCandidat.nbSommet; j++){
				if(i != j)
					AntListeCandidat.distances.get(i).add(new Arc(j,AntListeCandidat.antInstance.getDistance(i, j)));
			}
			
			Collections.sort(AntListeCandidat.distances.get(i));
		}	
	}
	
	/**constructeur de la liste de noeuds candidats pour une fourmi
	 * @throws Exception
	 */
	public AntListeCandidat() throws Exception{
		this.noeudAVisiter = new boolean[this.nbSommet];
		this.noeudVisite = 0;
	}
	
	/**méthode qui initialise tous les noeuds à visiter à true
	 */
	public void init(){
		this.noeudVisite = 0;
		for (int i=0; i<this.nbSommet; i++){
			this.noeudAVisiter[i] = true;
		}
	}
	
	/**fonction qui retourne true si tous les noeuds ont été visités, false sinon
	 * @return
	 */
	public boolean isEmpty(){
		return this.noeudVisite == this.nbSommet;
	}
	
	/**méthode qui définit le nombre de noeuds voisins
	 * @param n
	 */
	public void setNbNoeudsVoisins(int n) {
		if(n > this.nbSommet-2){
			n = this.nbSommet-2;
		}
		this.nbNoeudsVoisins = n;
	}
	
	/**fonction qui retourne le nombre de noeuds voisins
	 * @return
	 */
	public int getNbNoeudsVoisins(){
		return this.nbNoeudsVoisins;
	}
	
	/**fonction qui retourne le nombre de noeuds voisins
	 * @param i
	 * @param n
	 * @return
	 */
	public int getNoeudSuivant(int i, int n) {
		return this.distances.get(i).get(n).getNumeroNoeudArrive();
	}
	
	/**fonction qui retourne la liste des noeuds à visiter
	 * @param i
	 * @return
	 */
	public ArrayList<Integer> getNoeudAVisiter(int i){
		//on regarde si un noeud voisin est encore a visiter
		int NoeudSuivantAVisiter = -1;
		
		for(int n = 0; n < this.nbNoeudsVoisins && NoeudSuivantAVisiter == -1; n++){
			if(this.noeudAVisiter[this.getNoeudSuivant(i, n)]){
				NoeudSuivantAVisiter = this.getNoeudSuivant(i, n);
			}
		}
		
		ArrayList<Integer> noeudsAVisiter = new ArrayList<Integer>();
		//si oui
		if(NoeudSuivantAVisiter != -1){
			for(int n = 0; n < this.nbNoeudsVoisins; n++){
				if(this.noeudAVisiter[this.getNoeudSuivant(i, n)]){
					noeudsAVisiter.add(this.getNoeudSuivant(i, n));
				}
			}
		}
		else{
			for(int n = this.nbNoeudsVoisins; n < this.nbSommet -1; n++){
				if(this.noeudAVisiter[this.getNoeudSuivant(i, n)]){
					noeudsAVisiter.add(this.getNoeudSuivant(i, n));
				}
			}
		}
		Collections.shuffle(noeudsAVisiter);
		return noeudsAVisiter;
	}
	
	/**méthode qui permet de retirer un noeud de la liste en passant son boolean à false
	 * @param noeud
	 */
	public void retirer(int noeud){
		this.noeudAVisiter[noeud] = false;
		this.noeudVisite++;
	}
	

}
